package week06

import "math"

// 121. 买卖股票的最佳时机
// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

func maxProfit(prices []int) int {
	var dp = make([][][]int, len(prices)+1)
	for i := range dp {
		dp[i] = make([][]int, 2)
		for j := range dp[i] {
			dp[i][j] = []int{math.MinInt32, math.MinInt32}
		}
	}
	dp[0][0][0] = 0
	for i := 1; i <= len(prices); i++ {
		for j := 0; j <= 1; j++ {
			for k := 0; k <= 1; k++ {
				dp[i][j][k] = dp[i-1][j][k]
				if j == 0 {
					dp[i][0][k] = max(dp[i][0][k], dp[i-1][1][k] + prices[i-1])
				} else if j == 1 && k > 0 {
					dp[i][1][k] = max(dp[i][1][k], dp[i-1][0][k-1] - prices[i-1])
				}
			}

		}
	}
	return dp[len(prices)][0][1]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}